package 力扣_树算法.遍历.根据遍历构建二叉树;


import java.util.HashMap;
import java.util.Map;

/**105.从前序与中序遍历序列构造二叉树
 * @author zx
 * @create 2022-04-13 17:44
 */
public class Num105 {
    /**
     1.不断从前序结果集中取出元素，此元素作为当前树的根节点
     2.拿着根节点去中序遍历中查找该节点值所处的位置，数的左侧就是左子树，右侧就是右子树
     3.递归上述流程，直到前序遍历结果集全部遍历结束。
     */
    //表示前序遍历结果集的索引
    private int index = 0;
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        return buildTreeByPreOrder(preorder,inorder,0,preorder.length - 1);
    }
    //在preOrder的[left...right]借助中序遍历还原二叉树,返回二叉树的根节点
    private TreeNode buildTreeByPreOrder(int[] preorder,int[] inorder,int left,int right){
        //递归出口
        if(left > right){
            return null;
        }
        if(index == preorder.length){
            return null;
        }
        TreeNode root = new TreeNode(preorder[index]);
        index++;
        int pos = findIndex(inorder,root.val);
        // 之所以能将树的左右节点连接靠的就是终止条件以及root.left = 递归函数的返回值。
        root.left = buildTreeByPreOrder(preorder,inorder,left,pos - 1);
        root.right = buildTreeByPreOrder(preorder,inorder,pos + 1,right);
        return root;
    }
    //找到给定值在中序遍历中的索引
    private int findIndex(int[]inorder,int val){
        for(int i = 0;i < inorder.length;i++){
            if(val == inorder[i]){
                return i;
            }
        }
        return -1;
    }


    /**
     将索引用map存储后,可以减少每次都调用方法查找索引,提高效率
     */
    //表示前序遍历结果集的索引
//    private int index = 0;
    Map<Integer,Integer> map = new HashMap<>();
    public TreeNode buildTree2(int[] preorder, int[] inorder) {
        for(int i = 0;i < inorder.length;i++){
            map.put(inorder[i],i);
        }
        return buildTreeByPreOrder(preorder,0,preorder.length - 1);
    }
    //在preOrder的[left...right]借助中序遍历还原二叉树,返回二叉树的根节点
    //中序遍历数组中,按照中序遍历的数值,再前序遍历中找到对应的坐标,左边是左子树,右边是右子树
    private TreeNode buildTreeByPreOrder(int[] preorder, int left, int right){
        if(left > right){
            return null;
        }
        TreeNode root = new TreeNode(preorder[index]);
        index++;
        int pos = map.get(root.val);
        //之所以能将树的左右节点连接靠的就是终止条件以及root.left = 递归函数的返回值。
        root.left = buildTreeByPreOrder(preorder, left, pos - 1);
        root.right = buildTreeByPreOrder(preorder, pos + 1,right);
        return root;
    }
}

class TreeNode {
    public int val;
    TreeNode left;
    TreeNode right;
    TreeNode() {}
    TreeNode(int val) { this.val = val; }
    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}